#include "common.h"

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        int sz = s.size();
        int item_len = words[0].size();
        int left = 0, right = 0;
        unordered_map<string, int> nr_word;

        vector<int> result;
        for (auto &word : words)
        {
            nr_word[word]++;
        }

        for (int i = 0; i < item_len; ++i)
        {
            right = i;
            left = i;
            int cnt = 0;
            unordered_map<string, int> nr_item;
            while (right < sz)
            {
                string substring = s.substr(right, item_len);
                if (++nr_item[substring] <= nr_word[substring])
                    cnt++;
                right += item_len;
                if ((right - left) / item_len > words.size())
                {
                    // 出
                    if (nr_item[s.substr(left, item_len)]-- <= nr_word[s.substr(left, item_len)])
                        cnt--;
                    left += item_len;
                }
                if (cnt == words.size())
                {
                    result.push_back(left);
                }
            }
        }

        return result;
    }
};